package com.xw.class06;

import java.util.PriorityQueue;

/**
 * @author: xw
 * @create: 2022/11/7 15:00
 * @description: 已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k
 * k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序。
 */
public class Code03_SortedArrayDistanceLessK {

    public static void  sortedArrayDistanceLessK(int[] array,int k){
        if(k == 0){
            return;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index =0;

        for(;index <= Math.min(k-1, array.length-1);index++){
            heap.add(array[index]);
        }
        int  i= 0;
        for (;index < array.length;i++,index++){
            heap.add(array[index]);
            array[i] = heap.poll();
        }
        while(!heap.isEmpty()){
            array[i++] = heap.poll();
        }
    }
}
